A carry chain is a series of logical structures that together perform an overall function. Each logical structure typically has an output term and a carry out term that are functions of a carry input term from a prior logical structure in the series and an input term.
FIG. 1A shows a six bit incrementor function 100 implemented as a carry chain 100 having a sequence of six logical structures 101–106. Incrementers are functions that add a value (e.g., “1”) to an input value (e.g., a 000000 input corresponds to an output of 000001). Input terms of the incrementer function are presented on input nodes A0 through A5. The input terms are used to determine the output terms (on output nodes S0 through S5) of the incrementer function.
Logical structures 101 through 106 contain one or more functional units (e.g., functional unit 110 within logical structure 105) that typically accept one or more input terms and a carry input term to produce another output term or carry term. A functional unit effectively performs a logical operation upon or with its input value(s).
Referring to logical structure 105 as an example, note that the S4 output term depends upon the carry value 107 produced by a functional unit 108 (executed by the prior logical structure 104) and the fourth input term A4. Similar dependencies repeat themselves through the carry chain.
FIG. 1B shows a possible logical structure implementation 160. The logical structure 160 comprises a first look up table 161 (LUT) having three inputs 162 through 164. The look up table 161, which corresponds to a functional unit, may be used to effectively implement a logical operation upon or with the values presented at inputs 162 through 164. Note that an input (e.g., input 164) may be used as a carry input. The second lookup table 165 also receives inputs 162 through 164. The first look up table 161 may be used to generate an output term 166 while the second look up table 165 may be used to generate a carry output term 167.
Note that look up table 161 and 165 may be viewed as functional units within the logical structure 160. In alternate embodiments, the function provided by the look up tables may be enhanced (or otherwise added to) by other logic components within the logical structure (such as by a multiplexer that drives the carry output 167 or an XOR gate that drives the output 166). Actual logic may be used instead of look-up tables as well.
Significant amounts of time may be consumed by the carry chain 100 of FIG. 1A in order to execute the function. That is, referring to FIG. 1a, in order to fully execute the overall function represented by the carry chain 100 each logical structure 101–106 must be executed. Thus the total propagation delay of the carry chain 100 (and thus of the overall function) corresponds to the summed propagation delay over all logical structures 101–106. Because many vendors currently have a limit of one output term per logical structure, a logical structure has to be separately executed for each output term in the function performed by the carry chain. The time consumed as a result may be undesireable in various applications because each output term has to “wait” for all lower order terms to be determined beforehand.